Palindrome permutation

Time: O(N); Space: O(1); easy

Given a string, determine if a permutation of the string could form a palindrome.

Have you met this question in a real interview?

Example 1:

Input: s = “code”

Output: False

Explanation:

  • No solution

Example 2:

Input: s = “aab”

Output: True

Explanation:

  • “aab” –> “aba”

Example 3:

Input: s = “carerac”

Output: True

Explanation:

  • “carerac” –> “carerac”

[1]:

import collections

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def canPermutePalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        return sum(v % 2 for v in collections.Counter(s).values()) < 2

[3]:

sol = Solution1()
s = "code"
assert sol.canPermutePalindrome(s) == False
s = "aab"
assert sol.canPermutePalindrome(s) == True
s = "carerac"
assert sol.canPermutePalindrome(s) == True